///******************************************************************************
// *  Compilation:  javac DepthFirstOrder.java
// *  Execution:    java DepthFirstOrder digraph.txt
// *  Dependencies: Digraph.java Queue.java Stack.java StdOut.java
// *                EdgeWeightedDigraph.java DirectedEdge.java
// *  Data files:   http://algs4.cs.princeton.edu/42digraph/tinyDAG.txt
// *                http://algs4.cs.princeton.edu/42digraph/tinyDG.txt
// *
// *  Compute preorder and postorder for a digraph or edge-weighted digraph.
// *  Runs in O(E + V) time.
// *
// *  % java DepthFirstOrder tinyDAG.txt
// *     v  pre post
// *  --------------
// *     0    0    8
// *     1    3    2
// *     2    9   10
// *     3   10    9
// *     4    2    0
// *     5    1    1
// *     6    4    7
// *     7   11   11
// *     8   12   12
// *     9    5    6
// *    10    8    5
// *    11    6    4
// *    12    7    3
// *  Preorder:  0 5 4 1 6 9 11 12 10 2 3 7 8 
// *  Postorder: 4 5 1 12 11 10 9 6 0 3 2 7 8 
// *  Reverse postorder: 8 7 2 3 0 6 9 10 11 12 1 5 4 
// *
// ******************************************************************************/
//
//package algs4;
//
//import com.jimmysun.algorithms.chapter4_2.Digraph;
//import com.jimmysun.algorithms.chapter4_4.DirectedEdge;
//import com.jimmysun.algorithms.chapter4_4.EdgeWeightedDigraph;
//
///**
// *  The {@code DepthFirstOrder} class represents a data type for 
// *  determining depth-first search ordering of the vertices in a digraph
// *  or edge-weighted digraph, including preorder, postorder, and reverse postorder.
// *  <p>
// *  This implementation uses depth-first search.
// *  The constructor takes time proportional to <em>V</em> + <em>E</em>
// *  (in the worst case),
// *  where <em>V</em> is the number of vertices and <em>E</em> is the number of edges.
// *  Afterwards, the <em>preorder</em>, <em>postorder</em>, and <em>reverse postorder</em>
// *  operation takes take time proportional to <em>V</em>.
// *  <p>
// *  For additional documentation,
// *  see <a href="http://algs4.cs.princeton.edu/42digraph">Section 4.2</a> of
// *  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
// *
// *  @author Robert Sedgewick
// *  @author Kevin Wayne
// */
//public class DepthFirstOrder {
//    private boolean[] marked;          // marked[v] = has v been marked in dfs?
//    private int[] pre;                 // pre[v]    = preorder  number of v
//    private int[] post;                // post[v]   = postorder number of v
//    private Queue<Integer> preorder;   // vertices in preorder
//    private Queue<Integer> postorder;  // vertices in postorder
//    private int preCounter;            // counter or preorder numbering
//    private int postCounter;           // counter for postorder numbering
//
//    /**
//     * Determines a depth-first order for the digraph {@code G}.
//     * @param G the digraph
//     */
//    public DepthFirstOrder(Digraph G) {
//        pre    = new int[G.V()];
//        post   = new int[G.V()];
//        postorder = new Queue<Integer>();
//        preorder  = new Queue<Integer>();
//        marked    = new boolean[G.V()];
//        for (int v = 0; v < G.V(); v++)
//            if (!marked[v]) dfs(G, v);
//
//        assert check();
//    }
//
//    /**
//     * Determines a depth-first order for the edge-weighted digraph {@code G}.
//     * @param G the edge-weighted digraph
//     */
//    public DepthFirstOrder(EdgeWeightedDigraph G) {
//        pre    = new int[G.V()];
//        post   = new int[G.V()];
//        postorder = new Queue<Integer>();
//        preorder  = new Queue<Integer>();
//        marked    = new boolean[G.V()];
//        for (int v = 0; v < G.V(); v++)
//            if (!marked[v]) dfs(G, v);
//    }
//
//    // run DFS in digraph G from vertex v and compute preorder/postorder
//    private void dfs(Digraph G, int v) {
//        marked[v] = true;
//        pre[v] = preCounter++;
//        preorder.enqueue(v);
//        for (int w : G.adj(v)) {
//            if (!marked[w]) {
//                dfs(G, w);
//            }
//        }
//        postorder.enqueue(v);
//        post[v] = postCounter++;
//    }
//
//    // run DFS in edge-weighted digraph G from vertex v and compute preorder/postorder
//    private void dfs(EdgeWeightedDigraph G, int v) {
//        marked[v] = true;
//        pre[v] = preCounter++;
//        preorder.enqueue(v);
//        for (DirectedEdge e : G.adj(v)) {
//            int w = e.to();
//            if (!marked[w]) {
//                dfs(G, w);
//            }
//        }
//        postorder.enqueue(v);
//        post[v] = postCounter++;
//    }
//
//    /**
//     * Returns the preorder number of vertex {@code v}.
//     * @param  v the vertex
//     * @return the preorder number of vertex {@code v}
//     * @throws IllegalArgumentException unless {@code 0 <= v < V}
//     */
//    public int pre(int v) {
//        validateVertex(v);
//        return pre[v];
//    }
//
//    /**
//     * Returns the postorder number of vertex {@code v}.
//     * @param  v the vertex
//     * @return the postorder number of vertex {@code v}
//     * @throws IllegalArgumentException unless {@code 0 <= v < V}
//     */
//    public int post(int v) {
//        validateVertex(v);
//        return post[v];
//    }
//
//    /**
//     * Returns the vertices in postorder.
//     * @return the vertices in postorder, as an iterable of vertices
//     */
//    public Iterable<Integer> post() {
//        return postorder;
//    }
//
//    /**
//     * Returns the vertices in preorder.
//     * @return the vertices in preorder, as an iterable of vertices
//     */
//    public Iterable<Integer> pre() {
//        return preorder;
//    }
//
//    /**
//     * Returns the vertices in reverse postorder.
//     * @return the vertices in reverse postorder, as an iterable of vertices
//     */
//    public Iterable<Integer> reversePost() {
//        Stack<Integer> reverse = new Stack<Integer>();
//        for (int v : postorder)
//            reverse.push(v);
//        return reverse;
//    }
//
//
//    // check that pre() and post() are consistent with pre(v) and post(v)
//    private boolean check() {
//
//        // check that post(v) is consistent with post()
//        int r = 0;
//        for (int v : post()) {
//            if (post(v) != r) {
//                StdOut.println("post(v) and post() inconsistent");
//                return false;
//            }
//            r++;
//        }
//
//        // check that pre(v) is consistent with pre()
//        r = 0;
//        for (int v : pre()) {
//            if (pre(v) != r) {
//                StdOut.println("pre(v) and pre() inconsistent");
//                return false;
//            }
//            r++;
//        }
//
//        return true;
//    }
//
//    // throw an IllegalArgumentException unless {@code 0 <= v < V}
//    private void validateVertex(int v) {
//        int V = marked.length;
//        if (v < 0 || v >= V)
//            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
//    }
//
//    /**
//     * Unit tests the {@code DepthFirstOrder} data type.
//     *
//     * @param args the command-line arguments
//     */
//    public static void main(String[] args) {
//        In in = new In(args[0]);
//        Digraph G = new Digraph(in);
//
//        DepthFirstOrder dfs = new DepthFirstOrder(G);
//        StdOut.println("   v  pre post");
//        StdOut.println("--------------");
//        for (int v = 0; v < G.V(); v++) {
//            StdOut.printf("%4d %4d %4d\n", v, dfs.pre(v), dfs.post(v));
//        }
//
//        StdOut.print("Preorder:  ");
//        for (int v : dfs.pre()) {
//            StdOut.print(v + " ");
//        }
//        StdOut.println();
//
//        StdOut.print("Postorder: ");
//        for (int v : dfs.post()) {
//            StdOut.print(v + " ");
//        }
//        StdOut.println();
//
//        StdOut.print("Reverse postorder: ");
//        for (int v : dfs.reversePost()) {
//            StdOut.print(v + " ");
//        }
//        StdOut.println();
//
//
//    }
//
//}
//
///******************************************************************************
// *  Copyright 2002-2016, Robert Sedgewick and Kevin Wayne.
// *
// *  This file is part of algs4.jar, which accompanies the textbook
// *
// *      Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne,
// *      Addison-Wesley Professional, 2011, ISBN 0-321-57351-X.
// *      http://algs4.cs.princeton.edu
// *
// *
// *  algs4.jar is free software: you can redistribute it and/or modify
// *  it under the terms of the GNU General Public License as published by
// *  the Free Software Foundation, either version 3 of the License, or
// *  (at your option) any later version.
// *
// *  algs4.jar is distributed in the hope that it will be useful,
// *  but WITHOUT ANY WARRANTY; without even the implied warranty of
// *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// *  GNU General Public License for more details.
// *
// *  You should have received a copy of the GNU General Public License
// *  along with algs4.jar.  If not, see http://www.gnu.org/licenses.
// ******************************************************************************/
